package com.maishi.programmer.array;

/**
 * Created by brossdong on 2018/3/20.
 * 斐波那契数列
 */
public class TestFeibonaiqe10 {

    /**
     * 考虑时间复杂度
     * 不采用递归
     */
    public long Feibonaqie (int n) {

        /*int result = 0;
        int begin = 0;
        int start = 1;

        if (n == 0) return begin;

        if (n == 1) return start;

        for (int i = 2;i <= n;i++) {
            result = begin + start;
            begin = start;
            start = result;
        }
        return result;*/
        int arr[] = new int[n+1];
        arr[0]=0;
        arr[1]=1;
        for(int i=2;i<=n;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }

    public static void main(String[] args) {
        int a = 4;
        TestFeibonaiqe10 testFeibonaiqe = new TestFeibonaiqe10();
        long feibonaqie = testFeibonaiqe.Feibonaqie(a);
        System.out.println(feibonaqie);
    }

}
